1. Technical Field of the Invention
The present invention relates to a multi-material data labeling method and program for determining the insides/outsides of two-dimensional or three-dimensional boundary surfaces.
2. Description of Related Art
In the field of technology research and development, CAD (Computer Aided Design), CAM (Computer Aided Manufacturing), CAE (Computer Aided Engineering), CAT (Computer Aided Testing), and the like are used as simulation means for designing, machining, analyzing, and testing, respectively.
In addition, C-Simulation (Corporative Simulation) as continuous simulation, A-CAM (Advanced CAM) which also considers a machining process, and D-fabrication (Deterministic fabrication) providing ultimate accuracy are becoming widespread.
In the conventional simulation means mentioned above, the boundary surfaces of an object are important. For example, it is common practice to represent the object by the boundary surfaces, and the inside of the boundary surfaces is handled uniformly. In such a case, it is necessary to use an identification method for determining the insides/outsides of two-dimensional or three-dimensional boundary surfaces.
As conventional inside/outside determination methods, there are known (1) a ray crossing method, (2) a region growing (expanding) method using boundary tracking, (3) raster tracking in image processing, (4) multidirectional tracking, (5) a Curless method, (6) a Szeliski method and a Pulli method using an octree, Patent Document 1, Patent Document 2, and so on. Further, Patent Document 3 and Patent Document 4, both related to the present invention, were filed.
[Patent Document 1]
Japanese Laid-Open Patent Publication No. 09-81783.
[Patent Document 2]
Japanese Laid-Open Patent Publication No. 08-153214.
[Patent Document 3]
Japanese Laid-Open Patent Publication No. 2002-230054.
[Patent Document 4]
Japanese Patent Application No. 2002-142260, unpublished.
(1) In the region growing (expanding) method (ray crossing method), when an input boundary surface is present, the inside or outside of an object is determined based on whether the number of intersecting points between the boundary and each of rays (half-lines) emanating from a certain point is even or odd. That is, when the number of intersecting points is even, it is determined that the starting point (endpoint) of the ray is outside the object, or when the number of intersecting points is odd, it is determined that it is inside the object. This region growing (expanding) method is disclosed, for example, in Computational Geometry in C, second edition (J. O'Rourke, p. 246, Cambridge University Press, 1998).
However, the region growing (expanding) method cannot be applied to a case where rays come into accidental contact with a boundary, because this expansion has a repeated root so that two intersecting points will become one. It cannot also be applied to a case where there is a defect in boundary information (when data such as CAD data are read from different software, the data may be lost due to differences in representation or numerical value errors).
(2) The region growing (expanding) method using boundary tracking in image processing when only boundary information is given is disclosed in Digital Picture Processing (Rosenfeld & Kak, translated by Nagao, Kindaikagakusha, pp. 353-357), for example. However, since the processing is performed over the entire region, it takes time. Further, when there is a defect in surface information, the determination cannot be made properly.
(3) The raster tracking in image processing is disclosed in the above-mentioned book, Digital Picture Processing (p. 334). It is a method of tracking a boundary and a region sandwiched between boundaries while scanning cells along a coordinate axis such as an X axis. However, when a quantized image is formed from defective boundary information, for example when the surface is not a closed surface, proper determination cannot be made.
(4) In order to avoid this problem, multidirectional tracking (disclosed in the above-mentioned book, p. 332) can be used, but the efficiency of this method is low.
(5) The Curless method in the field of reverse engineering (for restructuring surface information from a group of measured points) is a robust method of defining, over the entire field, an implicit function based on distance using external information, such as regularly arranged measured points and plural camera directions to a measured object, to reconstruct surface information. This method is disclosed in “A volumetric method for building complex models from range images” (B. Curless and M. Levoy, In Proceedings of SIGGRAPH '96, pages 303-312, August 1996).
However, in the Curless method, since it is necessary to perform distance field calculations for all cells, this method has demerits in terms of data amount and calculation time. A problem of accuracy is also pointed out with this method, such as that the distance function cannot be calculated accurately for a structure thinner than the cell size or acute surface geometries. This results in an error in the determination.
(6) The Szeliski method (R. Szeliski, “Rapid octree construction from image sequences”) and the Pulli method (“Robust meshes from multiple range maps” by K. Pulli, T. Duchamp, H. Hoppe, J. McDonald, L. Hapiro, and W. Stuetzle in Proceedings of International Conference on Recent Advances in 3-D Digital Imaging and Modeling, May 1997, pp. 205-211), both using an octree, are methods of classifying, into the inside, outside, and boundary categories, the relations between several pieces of target range data (distance data) and cells generated by dividing space into an octree to reconstruct boundaries. These methods use projection operations for each cell, so that processing becomes complicated and takes time, resulting in unsteady calculations in the projection operations.
Patent Document 1 entitled “System and method for finite element model processing” is to judge whether the area of a target divided element agrees with the sum of the areas of triangles each having, as its vertices, nodes on the respective sides of the divided element and a node to be determined. However, there is a problem that this method cannot be applied to a case where there is a defect in the boundary information.
Patent Document 2 teaches an inside/outside determination method using voxels. This method has limitations that it is not available for hierarchization and it can cope with only two types of materials because of use of a data reversing operation.
Patent Document 4 entitled “Boundary data inside/outside judgment method and program thereof” supports “up to two types of materials per cell” in a data holding format described in Patent Document 3. This method is multi-material compliant from a broad view, or to put it in another way, it can handle only two type of materials per cell. Therefore, for rendering a state necessary to handle multiple materials, that is, such a state that three or more materials border one another, corresponding parts have to be divided finely more than necessary, or even such fine divisions may not be enough for accurate representation.